package 剑指offer;


/*
 * Author：江松
 * Date：2023/2/20 18:20

 * 二叉树:
 *
 * 树的子结构：找到相同值的节点，然后继续向下搜索比对
 * 可以采用层序遍历，递归遍历实现

 * 二叉树的镜像：后序遍历

 * 二叉树是否对称：从根节点向2个方向遍历，期间对比节点值
 *
 * 从上往下打印二叉树：层序遍历
 *
 * 二叉搜索树的后序遍历序列：
 二叉搜索树：left<root<right
 后序遍历：[left][right][root]---->倒序后，根就在前面了[root][right][left]
 （1）若ti<ti+1,说明ti+1是ti的“右子节点”
 （2）若ti>ti+1（序列下降），由根右左说明进入了左子树，
 ti+1的根节点（通过维护单调栈往前找）为局部左子树的根节点。
 这样保证了ti+1之后的值都小于root
 （3）满足1,2
 */

import org.omg.PortableInterceptor.INACTIVE;

import java.util.*;

public class Main4 {
    static Scanner scanner=new Scanner(System.in);
    class TreeNode{
        //String val;
        Integer val;
        TreeNode left;
        TreeNode right;
        TreeNode(Integer val){
            this.val=val;
        }
    }

    /**
     *
     * @param root 第一棵树的子节点=根节点值
     * @param root2 第二棵树的根
     * @return  判断子结构是否相等,以树2为基准进行遍历，树1跟随进行遍历判断
     */
    public boolean judgeSubTree(TreeNode root,TreeNode root2){
        Queue<TreeNode>queue2=new LinkedList<>();
        Queue<TreeNode>queue1=new LinkedList<>();
        queue2.offer(root2);
        queue1.offer(root);
        //遍历树2，树1做跟随即可
        while(!queue2.isEmpty()){
            TreeNode node1=queue1.poll();
            TreeNode node2=queue2.poll();
            //树1可能为空
            if(node1==null||node1.val!=node2.val){
                return false;
            }
            //树1做跟随，这样树1多出来的右子树也不会算进来
            if(node2.left!=null){
                queue1.offer(node1.left);
                queue2.offer(node2.left);
            }
            if(node2.right!=null){
                queue1.offer(node1.right);
                queue2.offer(node2.right);
            }
        }
        return true;
    }

    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1==null)return false;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root1);
        while(!queue.isEmpty()){
            TreeNode t=queue.poll();
            if(t.val==root2.val){
                if(judgeSubTree(t,root2))return true;
            }
            if(t.left!=null){
                queue.offer(t.left);
            }
            if(t.right!=null){
                queue.offer(t.right);
            }
        }
        return false;
    }

    //递归版本
    //以树2为基准，树1跟随遍历到结束，一直相等则正确反之错误
    public boolean check(TreeNode root1,TreeNode root2){
        if(root2==null)return true;
        if(root1==null || root1.val!=root2.val)return false;
        return check(root1.left,root2.left)&&check(root1.right,root2.right);
    }
    //遍历树1找到值与树2根值相同的点，然后进行判断
    public boolean HasSubtree2(TreeNode root1,TreeNode root2){
        if(root2==null)return false;
        if(root1==null)return false;
        boolean flag=false,flag1,flag2;
        if(root1.val==root2.val)flag=check(root1,root2);
        flag1=HasSubtree2(root1.left,root2);
        flag2=HasSubtree2(root1.right,root2);
        return flag||flag1||flag2;
    }





    //后序遍历
    public void dfsPost(TreeNode root){
        if(root==null)return;
        dfsPost(root.left);
        dfsPost(root.right);
        TreeNode tmp;
        tmp=root.left;
        root.left=root.right;
        root.right=tmp;
    }
    //二叉树镜像
    public TreeNode Mirror (TreeNode pRoot) {
        dfsPost(pRoot);
        return pRoot;
    }







    //向不同的方向进行搜索
    public boolean dfsDouble(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null)return true;
        if(root1==null||root2==null)return false;
        System.out.println("root1:"+root1.val+"---root2:"+root2.val);
        if(root1.val!=root2.val)return false;
        return dfsDouble(root1.left,root2.right)&&dfsDouble(root1.right,root2.right);
    }
    //判断二叉树是否对称
    public boolean isSymmetrical(TreeNode pRoot) {
        return dfsDouble(pRoot,pRoot);
    }





    //从上往下打印二叉树：层序遍历
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

        ArrayList<Integer>ans=new ArrayList<>();
        if(root==null)return ans;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode node=queue.poll();
            ans.add(node.val);
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        return ans;
    }

    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)return false;
        int root=Integer.MAX_VALUE;//维护根元素，进入左子树后，根比后面的都要大
        Stack<Integer>stack=new Stack<>();
        for(int i=sequence.length-1;i>=0;--i){
            if(sequence[i]>root)return false;
            while (!stack.isEmpty()&&sequence[i]<stack.peek()){
                root=stack.pop();//左子树结构的根节点，应该是最大的
            }
            stack.push(sequence[i]);
        }
        return true;
    }


    ArrayList<ArrayList<Integer>>ans=new ArrayList<>();
    LinkedList<Integer>path=new LinkedList<Integer>();
    int expectNumber;
    public void dfsPath(TreeNode root,int num){
        //搜索到根
        if(root==null)return;
        //加入当前节点
        num+=root.val;
        path.add(root.val);
        System.out.println("root:"+root.val+"---num:"+num);
        if(num==expectNumber&&root.left==null&&root.right==null){
            ans.add(new ArrayList<>(path));
            //不能return，因为还要删除当前节点
            //return;
        }
        //搜索左右子树
        dfsPath(root.left,num);
        dfsPath(root.right,num);
        //删除当前节点
        path.removeLast();
    }

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
        this.expectNumber=expectNumber;
        dfsPath(root,0);
        return ans;
    }














    public TreeNode createTree(){
        TreeNode node;
        Integer in=scanner.nextInt();//以空格结束，nextLine以换行结束
        if(in.equals("#")){
            node=null;
        }else{
            node=new TreeNode(in);
            node.left=createTree();
            node.right=createTree();
        }
        return node;
    }


    public void preOrder(TreeNode root){
        if(root!=null){
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    public void inOrder(TreeNode root){
        if(root!=null){
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }
    }

    public static void main(String[] args) {
        Main4 m4=new Main4();
        TreeNode root=m4.createTree();
        m4.preOrder(root);
        System.out.println();
        m4.inOrder(root);
    }
}
